package codingPractice.taotian;

import java.util.HashMap;
import java.util.Scanner;

/*
 * 小红拿到了一个数组，她想知道该数组有多少个子序列是排列。由于答案过大，请对10^9+7取模。
 * 排列是一个长度为k的数组，其中1到k都恰好出现一次。例如[2,3,1]是排列，而[1,3,3]、[1,5,2,3]则不是排列。
 * 子序列指数组取若干元素（可以不连续）按原数组顺序形成的新数组。
 * 
 * 输入描述
第一行输入一个正整数n，代表小红拿到的数组。第二行输入n个正整数ai，代表数组中的元素。
1<=n<=10^5
1<=ai<=10^9
输出描述
一个整数，代表子序列是排列的数量。

示例
输入
3
1 2 1

输出
4

输入
1
2
输出
0
 */


public class ZiXuLiePaiLie {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        scanner.nextLine();
        String[] number = scanner.nextLine().split(" ");
        int[] list = new int[n];
        for(int i=0;i<n;i++) {
            list[i] = Integer.parseInt(number[i]);
        }
        scanner.close();
        HashMap<Integer, Integer> hashMap = new HashMap<>();
        for(int num:list) {
            // hashMap.computeIfPresent(num, (key, value) -> value + 1);
            // hashMap.computeIfAbsent(num, key -> 1);
            if (hashMap.containsKey(num)) {
                hashMap.put(num, hashMap.get(num) + 1);
            } else {
                hashMap.put(num, 1);
            }
        }
        
        int res = 0;
        for(int i=1;i<=n;i++) {
            if(!hashMap.containsKey(i)) {
                break;
            } else {
                if (i == 1) {
                    res += hashMap.get(i);
                } else {
                    int newMul = hashMap.get(i) * res;
                    res += newMul;
                    res %= Math.pow(10, 9);
                }
                
            }
        }
        System.out.println(res);
        
    }
}
